package TDAList;
import java.util.Iterator;

/**
 * Implementación de la interfaz lista utilizando
 * una estructura doblemente enlazada y utizando
 * dos nodos dummies, uno al principio y otro al final.
 * 
 * @author Gonzalo Arró
 *
 * @param <E> tipo genérico para los elementos de la lista.
 */
public class DoublyLinkedList<E> implements PositionList<E> {
	
	// Atributos de instancia
	
	private DNodo<E> header, trailer;
	private int cantElementos;
	
	// Constructores
	
	public DoublyLinkedList () {
		header =  new DNodo<E>();
		trailer = new DNodo<E>();
		header.setSiguiente(trailer);
		trailer.setAnterior(header);
		cantElementos = 0;
	}
	
	// Métodos
	
	public int size () {
		// O(1)
		return cantElementos;
	}
	
	public boolean isEmpty () {
		// O(1)
		return cantElementos == 0;
	}
	
	public Position<E> first () throws EmptyListException {
		// O(1)
		if (isEmpty())
			throw new EmptyListException ("Lista vacía.");
		return (Position<E>) header.getSiguiente();
	}
	
	public Position<E> last () throws EmptyListException {
		// O(1)
		if (isEmpty())
			throw new EmptyListException ("Lista vacía.");
		return (Position<E>) trailer.getAnterior();
	}
	
	public Position<E> next (Position<E> p) throws InvalidPositionException, BoundaryViolationException {
		// O(1)
		DNodo<E> nodo = checkPosition(p);
		if (nodo.getSiguiente()==trailer)
			throw new BoundaryViolationException ("Fuera de rango.");
		return (Position<E>) nodo.getSiguiente();
	}
	
	public Position<E> prev (Position<E> p) throws InvalidPositionException, BoundaryViolationException {
		// O(1)
		DNodo<E> nodo = checkPosition(p);
		if (nodo.getAnterior()==header)
			throw new BoundaryViolationException ("Fuera de rango.");
		return (Position<E>) nodo.getAnterior();
	}
	
	public void addFirst (E e) {
		// O(1)
		DNodo<E> nuevoNodo = new DNodo<E>(e,header,header.getSiguiente());
		header.getSiguiente().setAnterior(nuevoNodo);
		header.setSiguiente(nuevoNodo);
		cantElementos++;
	}
	
	public void addLast (E e) {
		// O(1)
		DNodo<E> nuevoNodo = new DNodo<E>(e,trailer.getAnterior(),trailer);
		trailer.getAnterior().setSiguiente(nuevoNodo);
		trailer.setAnterior(nuevoNodo);
		cantElementos++;
	}
	
	public void addAfter (Position<E> p, E e) throws InvalidPositionException {
		// O(1)
		DNodo<E> nodo = checkPosition(p);
		DNodo<E> nuevoNodo = new DNodo<E>(e,nodo,nodo.getSiguiente());
		nodo.getSiguiente().setAnterior(nuevoNodo);
		nodo.setSiguiente(nuevoNodo);
		cantElementos++;
	}
	
	public void addBefore (Position<E> p, E e) throws InvalidPositionException {
		// O(1)
		DNodo<E> nodo = checkPosition(p);
		DNodo<E> nuevoNodo = new DNodo<E>(e,nodo.getAnterior(),nodo);
		nodo.getAnterior().setSiguiente(nuevoNodo);
		nodo.setAnterior(nuevoNodo);
		cantElementos++;
	}
	
	public E remove (Position<E> p) throws InvalidPositionException {
		// O(1)
		DNodo<E> nodo = checkPosition(p);
		E toReturn = nodo.element();
		nodo.getAnterior().setSiguiente(nodo.getSiguiente());
		nodo.getSiguiente().setAnterior(nodo.getAnterior());
		nodo.setSiguiente(null);
		nodo.setAnterior(null);
		nodo.setElemento(null);
		cantElementos--;
		return toReturn;
	}
	
	public E set (Position<E> p, E e) throws InvalidPositionException {
		// O(1)
		DNodo<E> nodo = checkPosition(p);
		E toReturn = nodo.element();
		nodo.setElemento(e);
		return toReturn;
	}
	
	public Iterator<E> iterator () {
		// O(1)
		return new ElementIterator<E>(this);
	}
	
	public Iterable<Position<E>> positions () {
		// O(n)
		try {
	    	PositionList<Position<E>> P = new DoublyLinkedList<Position<E>>();
	    	if (!isEmpty()){
		   		Position<E> p = first();
				while (true) {
					P.addLast(p);
					if (p== last())
						break;
					p = next(p);
				}
			}
	    	return P;
		}
		catch (EmptyListException | BoundaryViolationException | InvalidPositionException ex) {
			return null;
		}
	}
	
	/**
	 * Método que chequea si una posición es válida en la lista.
	 * 
	 * @param p la posición a chequear
	 * @return el nodo de la posición pasada por parámetro (si es válida).
	 * @throws InvalidPositionException si la posición pasada por parámetro no es válida.
	 */
	private DNodo<E> checkPosition (Position<E> p) throws InvalidPositionException {
		if (p==null || p==header || p==trailer)
			throw new InvalidPositionException ("La posición es inválida.");
		try {
			DNodo<E> toReturn = (DNodo<E>) p;
			if (toReturn.getAnterior()==null || toReturn.getSiguiente()==null)
				throw new InvalidPositionException ("La posición no es válida.");
			return toReturn;
		}
		catch (ClassCastException e) {
			throw new InvalidPositionException ("La posición no pertenece a esta lista.");
		}
	}

}
